/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2014 President and Fellows of Harvard College
 * Copyright (c) 2012-2014 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#ifndef KPERMUTER_HH
#define KPERMUTER_HH
#include "string.hh"

class identity_kpermuter {
  int size_;

 public:
  identity_kpermuter(int size) : size_(size) {}

  int size() const { return size_; }
  int operator[](int i) const { return i; }
  bool operator==(const identity_kpermuter&) const { return true; }
  bool operator!=(const identity_kpermuter&) const { return false; }
};

template <int C>
struct sized_kpermuter_info {};
template <>
struct sized_kpermuter_info<0> {
  typedef uint16_t storage_type;
  typedef unsigned value_type;
  enum { initial_value = 0x0120U, full_value = 0x2100U };
};
template <>
struct sized_kpermuter_info<1> {
  typedef uint32_t storage_type;
  typedef unsigned value_type;
  enum { initial_value = 0x01234560U, full_value = 0x65432100U };
};
template <>
struct sized_kpermuter_info<2> {
  typedef uint64_t storage_type;
  typedef uint64_t value_type;
  enum {
    initial_value = (uint64_t)0x0123456789ABCDE0ULL,
    full_value = (uint64_t)0xEDCBA98765432100ULL
  };
};

template <int width>
class kpermuter {
 public:
  typedef sized_kpermuter_info<(width > 3) + (width > 7) + (width > 15)> info;
  typedef typename info::storage_type storage_type;
  typedef typename info::value_type value_type;
  enum { max_width = (int)(sizeof(storage_type) * 2 - 1) };
  enum { size_bits = 4 };

  /** @brief Construct an uninitialized permuter. */
  kpermuter() {}
  /** @brief Construct a permuter with value @a x. */
  kpermuter(value_type x) : x_(x) {}

  /** @brief Return an empty permuter with size 0.

      Elements will be allocated in order 0, 1, ..., @a width - 1. */
  static inline value_type make_empty() {
    value_type p =
        (value_type)info::initial_value >> ((max_width - width) << 2);
    return p & ~(value_type)15;
  }
  /** @brief Return a permuter with size @a n.

      The returned permutation has size() @a n. For 0 <= i < @a n,
      (*this)[i] == i. Elements n through @a width - 1 are free, and will be
      allocated in that order. */
  static inline value_type make_sorted(int n) {
    value_type mask =
        (n == width ? (value_type)0 : (value_type)16 << (n << 2)) - 1;
    return (make_empty() << (n << 2)) | ((value_type)info::full_value & mask) |
           n;
  }

  /** @brief Return the permuter's size. */
  int size() const { return x_ & 15; }
  /** @brief Return the permuter's element @a i.
      @pre 0 <= i < width */
  int operator[](int i) const { return (x_ >> ((i << 2) + 4)) & 15; }
  int back() const { return (*this)[width - 1]; }
  value_type value() const { return x_; }
  value_type value_from(int i) const { return x_ >> ((i + 1) << 2); }

  void set_size(int n) { x_ = (x_ & ~(value_type)15) | n; }
  /** @brief Allocate a new element and insert it at position @a i.
      @pre 0 <= @a i < @a width
      @pre size() < @a width
      @return The newly allocated element.

      Consider the following code:
      <code>
      kpermuter<...> p = ..., q = p;
      int x = q.insert_from_back(i);
      </code>

      The modified permuter, q, has the following properties.
      <ul>
      <li>q.size() == p.size() + 1</li>
      <li>Given j with 0 <= j < i, q[j] == p[j] && q[j] != x</li>
      <li>Given j with j == i, q[j] == x</li>
      <li>Given j with i < j < q.size(), q[j] == p[j-1] && q[j] != x</li>
      </ul> */
  int insert_from_back(int i) {
    int value = back();
    // increment size, leave lower slots unchanged
    x_ = ((x_ + 1) & (((value_type)16 << (i << 2)) - 1))
         // insert slot
         |
         ((value_type)value << ((i << 2) + 4))
         // shift up unchanged higher entries & empty slots
         |
         ((x_ << 4) & ~(((value_type)256 << (i << 2)) - 1));
    return value;
  }
  /** @brief Insert an unallocated element from position @a si at position @a
     di.
      @pre 0 <= @a di < @a width
      @pre size() < @a width
      @pre size() <= @a si
      @return The newly allocated element. */
  void insert_selected(int di, int si) {
    (void)width;
    int value = (*this)[si];
    value_type mask = ((value_type)256 << (si << 2)) - 1;
    // increment size, leave lower slots unchanged
    x_ = ((x_ + 1) & (((value_type)16 << (di << 2)) - 1))
         // insert slot
         |
         ((value_type)value << ((di << 2) + 4))
         // shift up unchanged higher entries & empty slots
         |
         ((x_ << 4) & mask & ~(((value_type)256 << (di << 2)) - 1))
         // leave uppermost slots alone
         |
         (x_ & ~mask);
  }
  /** @brief Remove the element at position @a i.
      @pre 0 <= @a i < @a size()
      @pre size() < @a width

      Consider the following code:
      <code>
      kpermuter<...> p = ..., q = p;
      q.remove(i);
      </code>

      The modified permuter, q, has the following properties.
      <ul>
      <li>q.size() == p.size() - 1</li>
      <li>Given j with 0 <= j < i, q[j] == p[j]</li>
      <li>Given j with i <= j < q.size(), q[j] == p[j+1]</li>
      <li>q[q.size()] == p[i]</li>
      </ul> */
  void remove(int i) {
    (void)width;
    if (int(x_ & 15) == i + 1)
      --x_;
    else {
      int rot_amount = ((x_ & 15) - i - 1) << 2;
      value_type rot_mask = (((value_type)16 << rot_amount) - 1)
                            << ((i + 1) << 2);
      // decrement size, leave lower slots unchanged
      x_ = ((x_ - 1) & ~rot_mask)
           // shift higher entries down
           |
           (((x_ & rot_mask) >> 4) & rot_mask)
           // shift value up
           |
           (((x_ & rot_mask) << rot_amount) & rot_mask);
    }
  }
  /** @brief Remove the element at position @a i to the back.
      @pre 0 <= @a i < @a size()
      @pre size() < @a width

      Consider the following code:
      <code>
      kpermuter<...> p = ..., q = p;
      q.remove_to_back(i);
      </code>

      The modified permuter, q, has the following properties.
      <ul>
      <li>q.size() == p.size() - 1</li>
      <li>Given j with 0 <= j < i, q[j] == p[j]</li>
      <li>Given j with i <= j < @a width - 1, q[j] == p[j+1]</li>
      <li>q.back() == p[i]</li>
      </ul> */
  void remove_to_back(int i) {
    value_type mask = ~(((value_type)16 << (i << 2)) - 1);
    // clear unused slots
    value_type x = x_ & (((value_type)16 << (width << 2)) - 1);
    // decrement size, leave lower slots unchanged
    x_ = ((x - 1) & ~mask)
         // shift higher entries down
         |
         ((x >> 4) & mask)
         // shift removed element up
         |
         ((x & mask) << ((width - i - 1) << 2));
  }
  /** @brief Rotate the permuter's elements between @a i and size().
      @pre 0 <= @a i <= @a j <= size()

      Consider the following code:
      <code>
      kpermuter<...> p = ..., q = p;
      q.rotate(i, j);
      </code>

      The modified permuter, q, has the following properties.
      <ul>
      <li>q.size() == p.size()</li>
      <li>Given k with 0 <= k < i, q[k] == p[k]</li>
      <li>Given k with i <= k < q.size(), q[k] == p[i + (k - i + j - i) mod
     (size() - i)]</li>
      </ul> */
  void rotate(int i, int j) {
    value_type mask =
        (i == width ? (value_type)0 : (value_type)16 << (i << 2)) - 1;
    // clear unused slots
    value_type x = x_ & (((value_type)16 << (width << 2)) - 1);
    x_ = (x & mask) | ((x >> ((j - i) << 2)) & ~mask) |
         ((x & ~mask) << ((width - j) << 2));
  }
  /** @brief Exchange the elements at positions @a i and @a j. */
  void exchange(int i, int j) {
    value_type diff = ((x_ >> (i << 2)) ^ (x_ >> (j << 2))) & 240;
    x_ ^= (diff << (i << 2)) | (diff << (j << 2));
  }
  /** @brief Exchange positions of values @a x and @a y. */
  void exchange_values(int x, int y) {
    value_type diff = 0, p = x_;
    for (int i = 0; i < width; ++i, diff <<= 4, p <<= 4) {
      int v = (p >> (width << 2)) & 15;
      diff ^= -((v == x) | (v == y)) & (x ^ y);
    }
    x_ ^= diff;
  }

  lcdf::String unparse() const;

  bool operator==(const kpermuter<width>& x) const { return x_ == x.x_; }
  bool operator!=(const kpermuter<width>& x) const { return !(*this == x); }

  static inline int size(value_type p) { return p & 15; }

 private:
  value_type x_;
};

template <int width>
lcdf::String kpermuter<width>::unparse() const {
  char buf[max_width + 3], * s = buf;
  value_type p(x_);
  value_type seen(0);
  int n = p & 15;
  p >>= 4;
  for (int i = 0; true; ++i) {
    if (i == n) *s++ = ':';
    if (i == width) break;
    if ((p & 15) < 10)
      *s++ = '0' + (p & 15);
    else
      *s++ = 'a' + (p & 15) - 10;
    seen |= 1 << (p & 15);
    p >>= 4;
  }
  if (seen != (1 << width) - 1) {
    *s++ = '?';
    *s++ = '!';
  }
  return lcdf::String(buf, s);
}

template <typename T>
struct has_permuter_type {
  template <typename C>
  static char test(typename C::permuter_type*);
  template <typename>
  static int test(...);
  static constexpr bool value = sizeof(test<T>(0)) == 1;
};

template <typename T, bool HP = has_permuter_type<T>::value>
struct key_permuter {};
template <typename T>
struct key_permuter<T, true> {
  typedef typename T::permuter_type type;
  static type permutation(const T& n) { return n.permutation(); }
};
template <typename T>
struct key_permuter<T, false> {
  typedef identity_kpermuter type;
  static type permutation(const T& n) { return identity_kpermuter(n.size()); }
};

#endif
